package com.jia.leetCode;

import java.util.Arrays;

/**
 * @program: Leetcode
 * @description: https://leetcode.com/problems/out-of-boundary-paths/description/
 * @author: STU756
 * @create: 2020-08-21 17:04
 */
public class Pro0576 {
    int[][][] f;
    int mod = 1000000007;
    public int findPaths(int m, int n, int N, int i, int j) {
        this.f = new int[m][n][N+1];
        for(int a = 0; a < m; a++){
            for(int b = 0; b < n; b++) {
                Arrays.fill(f[a][b], -1);
            }
        }
        return dfs(m, n, N, i, j);
    }
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    private int dfs(int m, int n, int k, int x, int y) {
        if(k == 0) return 0;
        if(f[x][y][k] != -1) { return f[x][y][k];}
        f[x][y][k]  = 0;
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && nx < m && ny >= 0 && ny < n) {
                f[x][y][k] += dfs(m, n, k - 1, nx, ny);
                f[x][y][k] %= mod;
            } else{
                f[x][y][k]++;
            }
        }
        return f[x][y][k];
    }
}
